#include <iostream>
#include <vector>
using namespace std;

//堆调整函数
void MaxHeapify(vector<int>& v, int i, int heap_size) {
	int l = 2 * i + 1;
	int r = l + 1;
	int largest = i;
	if(l < heap_size && v[l] > v[largest]) 
		largest = l;
	if(r < heap_size && v[r] > v[largest]) 
		largest = r;
	if(largest != i) {
		swap(v[i], v[largest]);
		MaxHeapify(v, largest, heap_size);//被换下去的元素看下是否需要继续下沉
	}
}

void HeapSort1 (vector<int>& v) {
	int len = v.size();
	//建树
	for(int i = len / 2 - 1; i>=0; i--)
		MaxHeapify(v, i, len);
	//排序
	for(int i = len - 1; i > 0; i--) {
		swap(v[0], v[i]);
		MaxHeapify(v, 0, i);
	}
}


int main() {
	vector<int> v{1,4,3,2,7,9,5,0,4,10,6,3};
	for(auto& t : v)
		cout << t << " ";
	cout << endl;
	
	HeapSort1(v);
	
	for(auto& t : v)
		cout << t << " ";
	cout << endl;
	return 0;
}
